class Solution {
public:
    typedef struct DestInfo {
        string to;
        int *isUse;

        friend bool operator < (struct DestInfo const &a,struct DestInfo const &b) {  
            return (a.to < b.to);
        }
    } DestInfo;
    
    map<string, multiset<DestInfo>> map;
    vector<string> rst;
    vector<string> temp;

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        praseMap(tickets);

        temp.push_back("JFK");
        findItineraryStep(tickets, "JFK");

        return rst;
    }

    void findItineraryStep(vector<vector<string>>& tickets, string from) {
        if(temp.size() == tickets.size() + 1) {
            rst = temp;
            return;
        }

        auto iterator = map.find(from);
        if(iterator == map.end()){
            return;
        }

        for(set<DestInfo>::iterator i = iterator->second.begin(); i != iterator->second.end(); ++i){
            if(*i->isUse == 1) {
                continue;
            }

            *i->isUse = 1;
            temp.push_back(i->to);
            findItineraryStep(tickets, i->to);

            if(rst.empty() == false) {
                 return;
            }
            
            temp.pop_back();
            *i->isUse = 0;
        }
    }

    void praseMap(vector<vector<string>>& tickets){
        for(vector<string> ticket : tickets) {
            auto iterator = map.find(ticket[0]);
            if(iterator == map.end()) {
                map.insert({ticket[0], {{ticket[1], new int(0)}}});
            } else {
                iterator->second.insert({ticket[1], new int(0)});
            }
        }
    }
};